package main

import "fmt"

/*
数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
*/

/*
1^0=1
1^1=0
a^b=1

a^a=0
a^0=a
*/
func singleNumbers(nums []int) []int {
	res := 0
	for _, v := range nums {
		res ^= v
	}
	div := 1
	// 找到全员异或结果中为1的位。
	// 即可将全员分成该位为1和该位为0的两组
	// 出现过两次的数字在同一组，出现过一次的在不同组
	for (div & res) == 0 {
		div <<= 1
	}

	a, b := 0, 0

	for _, v := range nums {
		// 通过与运算进行分组
		if (v & div) == 0 {
			a ^= v
		} else {
			b ^= v
		}
	}

	return []int{a, b}
}

//哈希表
func singleNumbers1(nums []int) []int {
	hash := make(map[int]int)
	var res []int
	for _, i := range nums {
		hash[i]++
	}
	for i, v := range hash {
		if v == 1 {
			res = append(res, i)
		}
	}
	return res
}

func main() {
	n := []int{4, 1, 4, 6}
	fmt.Println(singleNumbers1(n))
}
